"""
Name: goslings.py
Author: Ben Goosman
Description: This is my AI for the icypc competition for the Fall 2011 
semester of the competitive programming class. I started with the example 
hunter.py and completely rewrote it.
"""

import random
import sys
import string
import math
import operator
from collections import deque

INFINITY=sys.maxint

# Width and height of the playing field.
SIZE = 31

# Number of children on each team.
CCOUNT = 4

# Quadrants
NW = 0
NE = 1
SW = 2
SE = 3

# Constants for the objects in each cell of the field
GROUND_EMPTY = 0  # Just powdered snow in this space.
GROUND_TREE = 1   # A tree in this space
GROUND_S = 2      # A small snowball in this space
GROUND_M = 3      # A medium snowball in this space
GROUND_MS = 4     # A small snowball on a medium one
GROUND_L = 5      # A large snowball in this space
GROUND_LM = 6     # A medium snowball on a large one.
GROUND_LS = 7     # A small snowball on a large one.
GROUND_SMR = 8    # A red Snowman in this space
GROUND_SMB = 9    # A blue Snowman in this space

# Constants for the things a child can be holding
HOLD_EMPTY = 0    # Child is holding nothing
HOLD_P1 = 1       # Child is holding one unit of powdered snow
HOLD_P2 = 2       # Child is holding two units of powdered snow
HOLD_P3 = 3       # Child is holding three units of powdered snow
HOLD_S1 = 4       # Child is holding one small snowball.
HOLD_S2 = 5       # Child is holding two small snowballs.
HOLD_S3 = 6       # Child is holding three small snowballs.
HOLD_M = 7        # Child is holding one medium snowball.
HOLD_L = 8        # Child is holding one large snowball.
POWDERED_SNOW = 1
SNOWBALL = 2

# Snow constants
SMALL = 1
MEDIUM = 2
LARGE = 3
ANY = 4

# Action constants
DONE = 0

# Constant for the red player color
RED = 0

# Constant for the blue player color
BLUE = 1

# Height for a standing child.
STANDING_HEIGHT = 9

# Height for a crouching child.
CROUCHING_HEIGHT = 6

# Maximum Euclidean distance a child can throw.
THROW_LIMIT = 24

# Maximum distance squared a child will attempt a throw
STANDING_THROWING_DISTANCE = 64
CROUCHING_THROWING_DISTANCE = 25

# Snow capacity limit for a space.
MAX_PILE = 9

# Snow that's too deep to move through.
OBSTACLE_HEIGHT = 6

# Height of a snowman
SNOWMAN_HEIGHT = 6

# Maximum height of all snow and snow objects in a cell
MAX_SNOW_HEIGHT = 9

# Constant used to mark child locations in the map, not used in this player.
GROUND_CHILD = 10

def DEBUG(msg):
	sys.stderr.write(msg + "\n")

# Representation of the game
class Game:
	def __init__(self):
		# Source of randomness
		self.rnd = random.Random()
		# State of the board at each turn
		self.board = Board(self, self.rnd)
		# Current game score for self (red) and opponent (blue).
		self.score = [0, 0]
		# List of children on the field, half for each team.
		self.all_children = []
		self.friends = []
		self.enemies = []

	def start(self):
		self.create_children()
		self.turnNum = string.atoi(sys.stdin.readline())
		from time import clock, time
		while self.turnNum >= 0:
			t1 = time()
			self.read_board()
			# Decide what each child should do
			for c in self.friends:
				move = c.act()
				if move is None:
					DEBUG("Bad move for " + str(c))
				self.write_action(move)
			self.board.reset()
			self.untarget_all_enemies()
			sys.stdout.flush()
			t2 = time()
			assert(t2-t1 < 0.5)
			self.turnNum = string.atoi(sys.stdin.readline())
	
	def write_action(self, m):
		assert(m is not None)
		if m.dest is None:
			assert(m.action is not None)	
			out = "%s\n" % m.action
			sys.stdout.write(out)
		else:
			if isinstance(m.dest, Cell):
				assert(m.action is not None and m.dest.pos.x is not None and m.dest.pos.y is not None)
				out = "%s %d %d\n" % (m.action, m.dest.pos.x, m.dest.pos.y)
				sys.stdout.write(out)
			elif isinstance(m.dest, Point):
				assert(m.action is not None and m.dest.x is not None and m.dest.y is not None)
				out = "%s %d %d\n" % (m.action, m.dest.x, m.dest.y)
				sys.stdout.write(out)
			elif isinstance(m.dest, Child):
				assert(m.action is not None and m.dest.cell.pos.x is not None and m.dest.cell.pos.y is not None)
				out = "%s %d %d\n" % (m.action, m.dest.cell.pos.x, m.dest.cell.pos.y)
				sys.stdout.write(out)
	
	def create_children(self):
		quadrants = [NW, SW, NE, SE]
		#quadrants = [SW, SW, SW, SW]
		for i in range(CCOUNT):
			c = Child(self, index=i, color=RED, initial_move_quadrant=quadrants[i])
			self.friends.append(c)
			self.all_children.append(c)
		for i in range(CCOUNT, CCOUNT * 2):
			c = Child(self, index=i, color=BLUE)
			self.enemies.append(c)
			self.all_children.append(c)

	def read_board(self):
		# read the scores of the two sides.
		tokens = string.split( sys.stdin.readline() )
		self.score[ RED ] = tokens[ 0 ]
		self.score[ BLUE ] = tokens[ 1 ]
		# Parse the current map.
		for i in range(SIZE):
			tokens = string.split( sys.stdin.readline() )
			for j in range(SIZE):
				cell = self.board.ground[i][j]
				# Can we see this cell?
				if tokens[j][0] == '*':
					cell.visible = False
				else:
					cell.height = string.find(string.digits, tokens[j][0])
					self.board.set_cell_holding(cell, tokens[j][1])
		# Read the states of all the children.
		i = 0
		for c in self.all_children:
			# Can we see this child?        
			tokens = string.split( sys.stdin.readline() )
			if tokens[0] == "*":
				c.visible = False
				c.last_known_cell = c.cell or None
				c.cell = None
			else:
				c.visible = True
				# Compute child color based on it's index.
				if i < CCOUNT:
					c.color = RED
				else:
					c.color = BLUE

				# Record the child's location.
				c.cell = self.board.get_cell(string.atoi(tokens[0]), string.atoi(tokens[1]))
				c.cell.drop(c)
			
				# Read the stance, what the child is holding and how much
				# longer he's dazed.
				c.standing = (tokens[2] == "S")
				c.set_holding(tokens[3])
				c.dazed = string.atoi(tokens[4])
			i += 1

	def untarget_all_enemies(self):
		for c in self.enemies:
			c.untarget()

# Representation of the game board
class Board:
	def __init__(self, game, rnd):
		self.game = game
		self.rnd = rnd
		# List of friendly snowmen
		self.snowmen = []
		# Allocate the whole field.
		self.ground = [[Cell(pos=Point(x, y)) for y in range(SIZE)] for x in range(SIZE)]

	def reset(self):
		for cell in self.all_cells():
			cell.free()
			cell.de_own()
		self.snowmen = []

	def add_snowman(self, snowman):
		self.snowmen.append(snowman)

	def is_good_snowman_position(self, child, color=RED):
		# Look at all the adjacent cells for a good location to build
		for cell in self.get_adj_cells(child):
			# Don't build near the edge
			boundary = 5
			if cell.pos.x < boundary or cell.pos.x > SIZE-boundary or cell.pos.y < boundary or cell.pos.y > SIZE-boundary:
				continue # Skip this cell
			# Compute how many cells we would gain if we built here
			potential_cell_gain = 0
			for cell_in_range in self.all_cells_in_range(cell=cell, distance=8):
				if not cell_in_range.is_owned():
					potential_cell_gain += 1
			if potential_cell_gain < 100:
				continue # Skip this cell
			# Don't build near other children if there are no snowmen on the board
			closest_dist = INFINITY
			if len(self.snowmen) == 0:
				for c in self.game.friends:
					if c is not child:
						dist = self.man_dist(c.cell, cell)
						if dist < closest_dist:
							closest_dist = dist
				if closest_dist < 6:
					continue
			return True # If we got this far, cell is a good snowman position

	def get_num_snowmen(self, color=ANY):
		num_snowmen = 0
		for snowman in self.snowmen:
			if color == ANY or snowman.color == color:
				num_snowmen += 1
		return num_snowmen

	def set_cell_holding(self, cell, code):
		cell.objects = [None]
		if code is "b":
			cell.drop(Tree())
		elif code is "c":
			cell.drop(Snowball(SMALL))
		elif code is "d":
			cell.drop(Snowball(MEDIUM))
		elif code is "e":
			cell.drop(Snowball(MEDIUM))
			cell.drop(Snowball(SMALL))
		elif code is "f":
			cell.drop(Snowball(LARGE))
		elif code is "g":
			cell.drop(Snowball(LARGE))
			cell.drop(Snowball(MEDIUM))
		elif code is "h":
			cell.drop(Snowball(LARGE))
			cell.drop(Snowball(SMALL))
		elif code is "i":
			s = Snowman(color=RED, cell=cell)
			self.add_snowman(s)
			cell.drop(s)
			self.refresh_domain(s)
		elif code is "j":
			s = Snowman(color=BLUE, cell=cell)
			self.add_snowman(s)
			cell.drop(s)
			self.refresh_domain(s)

	def refresh_domain(self, snowman):
		# Disregarding opponent, we now own cells with euclidean distance < 8
		for other_cell in self.all_cells_in_range(cell=snowman.cell, distance=8):
			if not other_cell.is_owned():
				# This snowman owns the cell if no other snowman owns it yet
				other_cell.own(owner=snowman)
			else:
				# Check who owns this cell
				distance_from_owner = self.euclid_dist(other_cell.snowman_owner.cell, other_cell)
				distance_from_snowman = self.euclid_dist(snowman.cell, other_cell)
				# If this snowman is closer, replace owner
				if distance_from_snowman < distance_from_owner:
					other_cell.own(owner=snowman)

	def man_dist(self, cell1, cell2):
		x = abs(cell2.pos.x - cell1.pos.x)
		y = abs(cell2.pos.y - cell1.pos.y)
		return x + y

	def euclid_dist(self, cell1, cell2):
		xdiff = cell2.pos.x - cell1.pos.x
		ydiff = cell2.pos.y - cell1.pos.y
		return xdiff * xdiff + ydiff * ydiff

	def in_throwing_distance(self, child, target_cell, if_standing=False):
		dist = self.euclid_dist(child.cell, target_cell)
		if (if_standing or child.standing) and dist < STANDING_THROWING_DISTANCE:
			return True
		if not child.standing and dist < CROUCHING_THROWING_DISTANCE:
			return True
		return False

	def any_throwing_obstacles(self, child, target_cell):
		cells = self.interpolate_path(child.cell, target_cell)
		for cell in cells:
			if not cell.is_empty():
				obj = cell.peek()
				# Children and Trees always block
				if obj is not None:
					return True
				if isinstance(obj, Tree) or isinstance(obj, Child) or isinstance(obj, Snowman):
					return True
		return False

	def any_moving_obstacles(self, child, target_cell):
		cells = self.interpolate_path(child.cell, target_cell)
		for cell in cells:
			if cell.is_claimed():
				return True
			if not cell.is_empty():
				obj = cell.peek()
				# Children, Trees, and Snowmen always block
				if isinstance(obj, Tree) or isinstance(obj, Child) or isinstance(obj, Snowman):
					return True
				# Cannot run through snow that is too high
				if cell.height >= OBSTACLE_HEIGHT:
					return True
		return False

	def interpolate_path(self, cell0, cell1):
		"""Compute a list of cells between two cells"""
		x1 = cell0.pos.x
		y1 = cell0.pos.y
		x2 = cell1.pos.x
		y2 = cell1.pos.y
		n = max(abs(x2-x1), abs(y2-y1))
		cells = []
		for t in range(1, n):
			x = int(x1 + round(float(t*(x2-x1))/float(n)))
			y = int(y1 + round(float(t*(y2-y1))/float(n)))
			cells.append(self.get_cell(x, y))
		return cells

	def pad_throwing_cell(self, child, target_cell, factor=2):
		xdiff = target_cell.pos.x - child.cell.pos.x
		ydiff = target_cell.pos.y - child.cell.pos.y
		return Point(target_cell.pos.x + xdiff * factor, target_cell.pos.y + ydiff * factor)		

	def get_rnd_cell(self, quadrant=None):
		x, y = None, None
		mid = (SIZE - 1) / 2
		if quadrant is None:
			x = self.rnd.randint(0, SIZE-1)
			y = self.rnd.randint(0, SIZE-1)
		else:
			if quadrant == NW:
				x = self.rnd.randint(mid/2, mid)
				y = self.rnd.randint(mid+mid/2, SIZE-1)
			elif quadrant == NE:
				x = self.rnd.randint(mid+mid/2, SIZE-1)
				y = self.rnd.randint(mid+mid/2, SIZE-1)
			elif quadrant == SW:
				x = self.rnd.randint(4, mid+mid/2)
				y = self.rnd.randint(4, mid+mid/2)
			elif quadrant == SE:
				x = self.rnd.randint(mid+mid/2, SIZE-1)
				y = self.rnd.randint(0, mid)
		return self.get_cell(x, y)

	def get_rnd_empty_cell(self, quadrant=None):
		while True:
			cell = self.get_rnd_cell(quadrant=quadrant)
			if cell.is_empty():
				return cell

	def get_rnd_empty_unowned_cell(self, quadrant=None):
		while True:
			cell = self.get_rnd_cell(quadrant=quadrant)
			if cell.is_empty() and (not cell.is_owned() or cell.snowman_owner.color == BLUE):
				return cell

	def get_rnd_close_cell(self, cell):
		close = 17
		minx = clamp(cell.pos.x - close, 0, SIZE-1)
		maxx = clamp(cell.pos.x + close, 0, SIZE-1)
		miny = clamp(cell.pos.y - close, 0, SIZE-1)
		maxy = clamp(cell.pos.y + close, 0, SIZE-1)
		x = self.rnd.randint(minx, maxx)
		y = self.rnd.randint(miny, maxy)
		return self.get_cell(x, y)

	def get_cell(self, x, y):
		return self.ground[x][y]

	def all_cells(self):
		for x in range(0, SIZE):
			for y in range(0, SIZE):
				yield self.get_cell(x, y)

	def all_cells_in_range(self, cell, distance, inclusive=False):
		for x in range(-1 * (distance), distance + 1):
			for y in range(-1 * (distance), distance + 1):
				p = Point(cell.pos.x + x, cell.pos.y + y)
				if self.in_board(p):
					other_cell = self.get_cell(p.x, p.y)
					dist = self.euclid_dist(cell, other_cell)
					dsq = distance * distance
					if ((not inclusive and dist < dsq) or (inclusive and dist <= dsq)):
						yield other_cell

	def get_adj_cells(self, child):
		cells = []
		for x in range(-1, 2):
			for y in range(-1, 2):
				if not (x == 0 and y == 0):
					p = Point(child.cell.pos.x + x, child.cell.pos.y + y)
					if (self.in_board(p)):
						cells.append(self.get_cell(p.x, p.y))
		return cells

	# From the list of cells a child can move to when standing, return the closest one to the target
	def local_search(self, child, target_cell):
		closest_cell = None
		# Generate list of (cell, distance_from_target) tuples
		cells = [(cell, self.euclid_dist(cell, target_cell)) for cell in self.find_reachable_empty_cells(child)]
		# Sort by distance
		cells.sort(key=operator.itemgetter(1))
		# If we already visited the closest cell, try the next one
		if cells[0][0] is child.last_visited_cell:
			return cells[1][0]
		return cells[0][0]

	def in_board(self, point):
		return (point.x >= 0 and point.x < SIZE and point.y >= 0 and point.y < SIZE)

	def find_close_enemies(self, child):
		threats = []
		for enemy in self.game.enemies:
			if enemy.visible and self.in_throwing_distance(child, enemy.cell, if_standing=True):
				threats.append(enemy)
		return threats

	def find_close_snowmen(self, child, color=ANY):
		snowmen = []
		close = 8
		for snowman in self.snowmen:
			if color == ANY or snowman.color == color:
				dist_from_child = self.man_dist(child.cell, snowman.cell)
				if dist_from_child < close:
					snowmen.append(snowman)
		return snowmen

	def find_adj_snowmen(self, child, color=ANY):
		cells = []
		for cell in self.get_adj_cells(child):
			obj = cell.peek()
			if isinstance(obj, Snowman) and (color == ANY or obj.color == color):
				cells.append(cell)
		return cells

	def find_adj_snowballs(self, child, size=ANY):
		cells = []
		for cell in self.get_adj_cells(child):
			obj = cell.peek()
			if isinstance(obj, Snowball) and (size == ANY or obj.size == size):
				cells.append(cell)
		return cells

	def find_adj_powdered_snow(self, child, debug=False):
		for cell in self.get_adj_cells(child):
			if cell.is_empty() and cell.height > 0 and not cell.is_claimed():
				return cell

	def find_adj_empty_cells(self, child):
		cells = []
		for cell in self.get_adj_cells(child):
			if cell.is_empty() and not cell.is_claimed():
				cells.append(cell)
		return cells

	def find_adj_empty_cell(self, child):
		for cell in self.get_adj_cells(child):
			if cell.is_empty() and not cell.is_claimed():
				return cell
	
	def find_reachable_empty_cells(self, child):
		cells = []
		for cell in self.all_cells_in_range(cell=child.cell, distance=2, inclusive=True):
			if not self.any_moving_obstacles(child, cell) and cell.is_empty() and not cell.is_claimed():
				cells.append(cell)
		return cells

	def sort_by_distance(self, origin_entity, entities):
		distances = [dict(entity=entity, distance=self.euclid_dist(origin_entity.cell, entity.cell)) 
				     for entity in entities]
		distances.sort(key=operator.itemgetter('distance')) # Sort by distance
		sorted_entities = [entity['entity'] for entity in distances] # Remove distances
		return sorted_entities


# Representation for a child in the game.
class Child:
	# Probabilities of catching and throwing
	# Assume prior probability of opponent catching to be 0.5
	num_failed_throws = 0.0
	num_throws = 1.0 
	num_attempted_catch = 50.0
	num_successful_catch = 50.0
	num_enemy_throw_chances = 1.0
	num_enemy_throw = 1.0

	def __init__(self, game, index, color, initial_move_quadrant=None):
		self.game = game
		self.board = game.board
		self.index = index
		self.standing = True
		self.dazed = False
		self.last_visited_cell = None
		self.targeted = False # Used to desiginate an enemy is targeted
		self.cell = None # The location of the child
		self.color = color # Side the child is on.
		self.holding = [] # What the child is holding in its hands.
		self.num_failed_catches = 0 # Turns we failed to catch a snowball
		self.attempted_catch = False
		self.attempted_throw_target = None
		# Save actions for reuse
		self.planter_action = PlanterAction(game=self.game, child=self,
			target_cell=self.board.get_rnd_empty_cell(quadrant=initial_move_quadrant))
		self.attack_action = AttackAction(game=self.game, child=self, target=None)
		self.replace_snowman_action = ReplaceSnowmanAction(game=self.game, child=self, snowman=None)

	def __str__(self):
		return "Child(" + str(self.cell.pos.x) + ", " + str(self.cell.pos.y) + ", " + str(self.color) + ")"

	def act(self):
		if self.dazed:
			Child.num_enemy_throw += 1
			return Move("idle")

		# Get a list of enemies in range of this child
		threats = self.board.sort_by_distance(self, self.board.find_close_enemies(self))
		num_threats = len(threats)
		targeted_enemy = False

		# Deal with any threats first
		if num_threats >= 1:
			# Keep track of how many times we failed to catch
			if self.attempted_catch:
				self.attempted_catch = False
				if self.num_held_snowballs + 1 == self.get_holding_count():
					Child.num_successful_catch += 1
					self.num_failed_catches = 0 # Reset if we caught one
				else:
					self.num_failed_catches += 1
			# Keep track of how many times opponent caught our snowballs
			if self.attempted_throw_target is not None:
				Child.num_throws += 1.0
				if not self.attempted_throw_target.dazed:
					Child.num_failed_throws += 1.0
				self.attempted_throw_target = None
			# Quit catching past a certain threshold
			if self.num_failed_catches < 2:
				# Attempt a catch
				for threat in threats:
					enemy = threat
					if (self.should_attempt_catch(enemy)):
						self.attempted_catch = True
						self.num_held_snowballs = self.get_holding_count()
						Child.num_attempted_catch += 1
						return Move("catch", enemy)
			# Attack closest untargeted threat
			for threat in threats:
				enemy = threat
				enemy_obj = enemy.peek_holding()
				if (not self.board.any_throwing_obstacles(enemy, self.cell) and
					not enemy.dazed and
					enemy.is_holding_snowball(size=SMALL, count=ANY)):
					Child.num_enemy_throw_chances += 1
				if (not enemy.is_targeted() and 
					not self.board.any_throwing_obstacles(enemy, self.cell) and
					(not coin_flip(Child.num_failed_throws / Child.num_throws) or 
					 enemy.dazed or
					 enemy.is_holding_snowball(size=MEDIUM, count=ANY) or
					 enemy.is_holding_snowball(size=LARGE, count=ANY) or
					 isinstance(enemy.peek_holding(), PowderedSnow))):
					enemy.target()
					self.attack_action.set_target(enemy)
					return self.attack_action.act()

		self.num_failed_catches = 0
		self.attempted_catch = False

		# Keep replacing a snowman we have already decided to replace
		if self.replace_snowman_action.get_snowman() is not None:
			if not self.replace_snowman_action.goal_state() and self.replace_snowman_action.get_target_cell().claim(owner=self):
				return self.replace_snowman_action.act()
		# Check for any snowmen we can replace
		snowmen = self.board.sort_by_distance(self, self.board.find_close_snowmen(self, color=BLUE))
		for snowman in snowmen:
			if snowman.cell.claim(owner=self):
				self.replace_snowman_action.set_snowman(snowman)
				return self.replace_snowman_action.act()

		# Default action is to roam and plant snowmen
		return self.planter_action.act()

	def can_catch(self):
		return ((self.peek_holding() is None or 
				 self.is_holding_snowball(size=SMALL, count=1) or 
				 self.is_holding_snowball(size=SMALL, count=2)) and
				not self.dazed)

	def should_attempt_catch(self, enemy):
		return (self.can_catch() and 
				enemy.is_holding_snowball(size=SMALL, count=ANY) and
				not enemy.dazed and
				not self.board.any_throwing_obstacles(enemy, self.cell) and
				coin_flip(Child.num_enemy_throw / Child.num_enemy_throw_chances))

	def is_targeted(self):
		return self.targeted

	def target(self):
		self.targeted = True

	def untarget(self):
		self.targeted = False

	def peek_holding(self):
		if not self.holding:
			return None
		return self.holding[0]

	def is_holding_snowball(self, count=ANY, size=ANY):
		if not self.holding:
			return False
		num_counted = 0
		for obj in self.holding:
			# Fail if not holding snowball
			if not isinstance(obj, Snowball):
				return False 
			# Fail on size mismatch
			if size != ANY and obj.size != size:
				return False
			num_counted += 1
			# Fail on count mismatch
			if count != ANY and num_counted > count:
				return False
		return True

	def get_holding_count(self):
		count = 0
		for obj in self.holding:
			count += 1
		return count

	def set_holding(self, code):
		self.holding = []
		if code is "a":
			pass # Child is not holding anything
		elif code is "b":
			self.holding.append(PowderedSnow(size=SMALL))
		elif code is "c":
			self.holding.append(PowderedSnow(size=MEDIUM))
		elif code is "d":
			self.holding.append(PowderedSnow(size=LARGE))
		elif code is "e":
			self.holding.append(Snowball(size=SMALL))
		elif code is "f":
			self.holding.append(Snowball(size=SMALL))
			self.holding.append(Snowball(size=SMALL))
		elif code is "g":
			self.holding.append(Snowball(size=SMALL))
			self.holding.append(Snowball(size=SMALL))
			self.holding.append(Snowball(size=SMALL))
		elif code is "h":
			self.holding.append(Snowball(size=MEDIUM))
		elif code is "i":
			self.holding.append(Snowball(size=LARGE))


"""
Action:
Base class for all actions
"""
class Action(object):
	def __init__(self, game, child):
		self.game = game
		self.board = game.board
		self.child = child


"""
PlanterAction:
Choose a random location to move
If child is in a suitable spot to build a snowman:
	Build snowman
Else:
	Move to target location
	If at target location, choose a new location
"""
class PlanterAction(Action):
	def __init__(self, target_cell=None, *args, **kwargs):
		super(PlanterAction, self).__init__(*args, **kwargs)
		self.make_snowman_action = MakeSnowmanAction(game=self.game, child=self.child)
		self.pickup_small_snowball_action = PickupSnowballAction(game=self.game, child=self.child, count=1, size=SMALL)
		self.move_action = MoveAction(game=self.game, child=self.child, target_cell=target_cell)

	def act(self):
		# Initialize target cell if it has not been initialized yet
		if self.move_action.get_target_cell() is None:
			self.target_cell = self.board.get_rnd_empty_cell()
			self.move_action.set_target_cell(self.target_cell)

		# If we reached target cell, pick a new one
		if self.move_action.goal_state():
			#self.target_cell = self.board.get_rnd_empty_cell()
			self.target_cell = self.board.get_rnd_empty_unowned_cell()
			self.move_action.set_target_cell(self.target_cell)
		
		# Start building a snowman if in a suitable position
		if self.board.is_good_snowman_position(self.child):
			# Keep building if not finished
			if not self.make_snowman_action.goal_state():
				return self.make_snowman_action.act()

		# Pick up a small snowball if we don't have one
		if not self.child.is_holding_snowball(size=SMALL, count=ANY):
			return self.pickup_small_snowball_action.act()
		# If we are on the move, drop everything except a small snowball
		if self.child.peek_holding() is not None and not self.child.is_holding_snowball(count=1, size=SMALL):
			return Move("drop", self.board.find_adj_empty_cell(self.child))

		return self.move_action.act()


"""
ReplaceSnowmanAction:
Replaces enemy snowmen on cells with height < 9
Destroys enemy snowmen on cells with height >= 9
"""
class ReplaceSnowmanAction(Action):
	def __init__(self, snowman=None, *args, **kwargs):
		super(ReplaceSnowmanAction, self).__init__(*args, **kwargs)
		self.snowman = snowman
		self.pickup_snowball_action = PickupSnowballAction(game=self.game, child=self.child, size=SMALL, count=1)
		self.make_snowman_action = MakeSnowmanAction(game=self.game, child=self.child)
		self.move_action = MoveAction(game=self.game, child=self.child, target_cell=None)

	def set_snowman(self, snowman):
		self.snowman = snowman

	def get_snowman(self):
		return self.snowman

	def get_target_cell(self):
		return self.snowman.cell

	def goal_state(self):
		obj = self.snowman.cell.peek()
		return (isinstance(obj, Snowman) and obj.color == RED) or (self.snowman.cell.height >= 9 and not isinstance(obj, PowderedSnow))

	def act(self):
		# Move next to the snowman
		self.move_action.set_target_cell(self.snowman.cell)

		# Check if we are in the correct position to replace the snowman
		if self.move_action.next_to_target():
			if isinstance(self.snowman.cell.peek(), Snowman):
				# If we have a small snowball drop it on snowman if we can or on any cell
				if self.child.is_holding_snowball(size=SMALL, count=ANY) and self.snowman.cell.height < 9:
					return Move("drop", self.snowman.cell)
				self.pickup_snowball_action.set_pickup_cell(self.snowman.cell)
				return self.pickup_snowball_action.act()
			# Pick up a small snowball if we don't have one
			if not self.child.is_holding_snowball(size=SMALL, count=ANY):
				self.pickup_snowball_action.set_pickup_cell(None)
				return self.pickup_snowball_action.act()
			return Move("drop", self.snowman.cell)

		# Move to a cell adj to the snowman from which we can replace it
		return self.move_action.act()


"""
IdleAction:
Just return an idle move
"""
class IdleAction(Action):
	def __init__(self, *args, **kwargs):
		super(IdleAction, self).__init__(*args, **kwargs)

	def act(self):
		return Move("idle")


"""
MakeSnowmanAction:
If there are no adjacent snowballs to child:
	Pickup large snowball
	Place large snowball in the tallest square that can hold a snowman
Else:
	If we find a large snowball:
		If that square can hold a snowman:
			Pickup medium snowball
			Place medium snowball on large snowball
	If we find a medium snowball:
		If there is a large snowball underneath:
			If that square can hold a snowman:
				Pickup small snowball
				Place small snowball on medium snowball
"""
class MakeSnowmanAction(Action):
	def __init__(self, *args, **kwargs):
		super(MakeSnowmanAction, self).__init__(*args, **kwargs)
		self.pickup_small_snowball_action = PickupSnowballAction(game=self.game, child=self.child, count=1, size=SMALL)
		self.pickup_medium_snowball_action = PickupSnowballAction(game=self.game, child=self.child, count=1, size=MEDIUM)
		self.pickup_large_snowball_action = PickupSnowballAction(game=self.game, child=self.child, count=1, size=LARGE)

	def goal_state(self):
		cells = self.board.find_adj_snowmen(self.child, color=RED)
		return len(cells) >= 1

	def act(self):
		if self.goal_state():
			return Move("done")
		else:
			# Look for adj snowballs
			cells = self.board.find_adj_snowballs(self.child)
			for cell in cells:
				snowball = cell.peek()
				# If we find a large snowball, place a medium snowball on it
				if snowball.size == LARGE:
					if cell.height + 3 <= MAX_SNOW_HEIGHT and cell.claim(owner=self.child):
						if self.child.is_holding_snowball(count=1, size=MEDIUM):
							return Move("drop", cell)
						else:
							return self.pickup_medium_snowball_action.act()	
				# If we find a medium snowball
				elif snowball.size == MEDIUM:
					# If there is a large snowball under it, place a small snowball on it
					obj_under_top = cell.peek(2)
					if isinstance(obj_under_top, Snowball) and obj_under_top.size == LARGE:
						if cell.height + 1 <= MAX_SNOW_HEIGHT and cell.claim(owner=self.child):
							if self.child.is_holding_snowball(count=1, size=SMALL):
								return Move("drop", cell)
							else:
								return self.pickup_small_snowball_action.act()
			# If we got this far, place a large snowball
			if self.child.is_holding_snowball(count=1, size=LARGE):
				cells = self.board.find_adj_empty_cells(self.child)
				tallest_valid_cell = None 
				for c in cells:
					height_with_snowman = c.height + SNOWMAN_HEIGHT
					if height_with_snowman <= MAX_SNOW_HEIGHT:
						if tallest_valid_cell is None or c.height > tallest_valid_cell.height:
							tallest_valid_cell = c
				tallest_valid_cell.claim(owner=self.child)
				return Move("drop", tallest_valid_cell)
			else:
				return self.pickup_large_snowball_action.act()
		DEBUG("MakeSnowmanAction")


"""
AttackAction:
Update throw action with target cell
Throw at target
"""
class AttackAction(Action):
	def __init__(self, target, *args, **kwargs):
		super(AttackAction, self).__init__(*args, **kwargs)
		self.target = target
		self.throw_action = None

	def set_target(self, target):
		self.target = target
		self.throw_action = ThrowAction(game=self.game, child=self.child, target_cell=target.cell)

	def act(self):
		self.throw_action.set_target_cell(self.target.cell)
		move = self.throw_action.act()
		if (move.action is "throw" and
			self.target.can_catch()):
			self.child.attempted_throw_target = self.target
			self.target.num_held_snowballs = self.target.get_holding_count()
		return move


"""
ThrowAction:
If holding a small snowball:
	If in throwing distance of target cell:
		If there are no obstacles in the way of throwing
			Throw past the target
		Else:
			Move closer to the target
	Else:
		Stand if crouching
		If standing, move closer
"""
class ThrowAction(Action):
	def __init__(self, target_cell, *args, **kwargs):
		super(ThrowAction, self).__init__(*args, **kwargs)
		self.target_cell = target_cell
		self.pickup_snowball_action = PickupSnowballAction(game=self.game, child=self.child)
		self.move_action = MoveAction(game=self.game, child=self.child, target_cell=self.target_cell)

	def goal_state(self):
		return False

	def set_target_cell(self, target_cell):
		self.target_cell = target_cell
		self.move_action.set_target_cell(target_cell)

	def act(self):
		# Try to throw if we have a snowball
		if self.child.is_holding_snowball(size=SMALL, count=ANY):
			if self.board.in_throwing_distance(self.child, self.target_cell):
				if not self.board.any_throwing_obstacles(self.child, self.target_cell):
					return Move("throw", self.board.pad_throwing_cell(self.child, self.target_cell))
				else:
					return self.move_action.act()
			else:
				# Try standing
				if not self.child.standing:
					return Move("stand")
				# Move closer
				else:
					return self.move_action.act()
		else:
			# Pickup a snowball
			return self.pickup_snowball_action.act()
		DEBUG("ThrowAction")


"""
PickupSnowballAction:
If holding less than what child needs, pick up more
If holding too much, drop what child is holding
"""
class PickupSnowballAction(Action):
	def __init__(self, count=1, size=SMALL, *args, **kwargs):
		super(PickupSnowballAction, self).__init__(*args, **kwargs)
		self.count = count
		self.size = size
		self.pickup_cell = None

	def goal_state(self):
		return self.child.is_holding_snowball(count=self.count, size=self.size)

	def set_pickup_cell(self, cell):
		self.pickup_cell = cell

	def act(self):
		top = self.child.peek_holding()
		# Holding snowball(s)
		if isinstance(top, Snowball):
			# Holding incorrect size of snowball
			if top.size != self.size:
				cell = self.board.find_adj_empty_cell(self.child)
				assert(cell is not None)
				if cell is not None and cell.claim(owner=self.child):
					return Move("drop", cell)
			if top.size == self.size and self.pickup_cell is not None:
				if self.child.standing:
					return Move("crouch")
				return Move("pickup", self.pickup_cell)
			# Holding correctly sized snowballs, but we don't have enough
			holding_count = self.child.get_holding_count()
			if top.size == self.size and holding_count < self.count:
				# Try to find a snowball to pickup	
				cells = self.board.find_adj_snowballs(self.child, size=SMALL)
				if len(cells) + holding_count >= self.count and Cell.all_unclaimed(cells):
					# Claim all the cells and pick up one of them at a time
					Cell.claim_all(cells, owner=self.child)
					assert(cells[0] is not None)
					if self.child.standing:
						return Move("crouch")
					return Move("pickup", cells[0])
				else:
					# Drop the snowball somewhere safe so we can pick up more powdered snow
					cell = self.board.find_adj_empty_cell(self.child)
					if cell is not None and cell.claim(owner=self.child):
						return Move("drop", cell)
		# Holding powdered snow
		elif isinstance(top, PowderedSnow):
			if top.size == self.size:
				return Move("crush")
			# Holding less powdered snow than we want
			elif top.size < self.size:
				if self.pickup_cell is not None and self.pickup_cell.claim(owner=self.child):
					if self.child.standing:
						return Move("crouch")
					return Move("pickup", self.pickup_cell) 
				cell = self.board.find_adj_powdered_snow(self.child)
				if cell is not None and cell.claim(owner=self.child):
					if self.child.standing:
						return Move("crouch")
					return Move("pickup", cell) 
			# Holding too much powdered snow
			elif top.size > self.size:
				cell = self.board.find_adj_empty_cell(self.child)
				if cell is not None and cell.claim(owner=self.child):
					return Move("drop", cell)
		# Holding nothing
		elif top is None:
			# Try to find a snowball to pickup	
			cells = self.board.find_adj_snowballs(self.child, size=self.size)
			if len(cells) >= self.count and Cell.all_unclaimed(cells):
				# Claim all the cells and pick up one of them at a time
				Cell.claim_all(cells, owner=self.child)
				if self.child.standing:
					return Move("crouch")
				return Move("pickup", cells[0])
			else:
				# Start making a snowball
				if self.pickup_cell is not None and self.pickup_cell.claim(owner=self.child):
					if self.child.standing:
						return Move("crouch")
					return Move("pickup", self.pickup_cell) 
				cell = self.board.find_adj_powdered_snow(self.child)
				if cell is not None and cell.claim(owner=self.child):
					if self.child.standing:
						return Move("crouch")
					return Move("pickup", cell) 
		# Move somewhere random if we cannot pickup any more snow or we cannot drop what we have
		cell = self.board.find_adj_empty_cell(self.child)
		if cell is not None and cell.claim(owner=self.child):
			if self.child.standing:
				return Move("run", cell)
			else:
				return Move("stand")
		# We shouldn't get here
		DEBUG("PickupSnowballAction")


"""
MoveAction:
Attempt to move to target location in the fastest way possible
"""
class MoveAction(Action):
	def __init__(self, target_cell, *args, **kwargs):
		super(MoveAction, self).__init__(*args, **kwargs)
		self.target_cell = target_cell
		self.move_tries = 0

	def goal_state(self):
		return self.child.cell.pos.x == self.target_cell.pos.x and self.child.cell.pos.y == self.target_cell.pos.y

	def set_target_cell(self, target_cell):
		self.target_cell = target_cell

	def get_target_cell(self):
		return self.target_cell

	def next_to_target(self):
		cells = self.board.get_adj_cells(self.child)
		for cell in cells:
			if cell is self.target_cell:
				return True
		return False

	def act(self):
		# Move the child toward the given target location
		if self.goal_state():
			self.child.last_visited_cell = None
			return Move("done")
		if not self.child.standing:
			return Move("stand")
		elif self.child.standing:
			# If we are next to the target and it's occupied, try a few times before giving up
			if self.next_to_target() and not self.target_cell.is_empty():
				if self.move_tries >= 3:
					new_cell = self.board.get_rnd_empty_cell()
					self.set_target_cell(new_cell)
				else:
					self.move_tries += 1
			# Run to the destination
			cell = self.board.local_search(self.child, self.target_cell)
			path = self.board.interpolate_path(self.child.cell, cell)
			for c in path:
				c.claim(owner=self.child)
			cell.claim(owner=self.child)
			self.child.last_visited_cell = cell
			return Move("run", cell)
		DEBUG("MoveAction")


# Representation of a cell on the board
class Cell:
	def __init__(self, pos, height=0, claimed=False, visible=False, has_child=False):
		self.pos = pos
		self.height = height
		self.objects = [None]
		self.visible = visible
		self.has_child = has_child
		self.owner = None

	def __str__(self):
		return str("(" + str(self.pos.x) + ", " + str(self.pos.y) + ")")

	def drop(self, obj):
		top = self.peek()
		# Tree
		if isinstance(obj, Tree) and top is None:
			self.objects.append(obj)
			return True
		# PowderedSnow
		elif isinstance(obj, PowderedSnow) and top is None:
			return True
		# Snowball
		elif isinstance(obj, Snowball):
			if top is None:
				self.objects.append(obj)
				return True
			elif isinstance(top, Snowball):
				if top.size > obj.size:
					self.objects.append(obj)
					return True
				elif top.size <= obj.size:
					# Crush all snowballs in this cell
					self.objects = [None]
					return True
		# Child
		elif isinstance(obj, Child):
			if self.is_empty():
				self.objects.append(obj)
		# Snowman
		elif isinstance(obj, Snowman):
			if self.is_empty():
				self.objects.append(obj)
		return False

	def pickup(self):
		return self.objects.pop()

	def peek(self, depth=1):
		return self.objects[-1 * depth]

	def is_claimed(self):
		return self.owner is not None

	def claim(self, owner):
		if self.owner is None:
			self.owner = owner
			return True
		return self.owner is owner

	def free(self):
		self.owner = None

	def is_owned(self):
		return self.snowman_owner is not None

	def own(self, owner):
		self.snowman_owner = owner

	def de_own(self):
		self.snowman_owner = None

	def is_empty(self):
		return self.peek() is None;

	@staticmethod
	def all_unclaimed(cells):
		for cell in cells:
			if cell.is_claimed():
				return False
		return True

	@staticmethod
	def claim_all(cells, owner):
		for cell in cells:
			cell.claim(owner=owner)

# Snowman
class Snowman:
	def __init__(self, color, cell=None):
		self.color = color
		self.cell = cell

	def __str__(self):
		color = "red"
		if self.color == BLUE:
			color = "blue"
		return "Snowman(" + str(self.cell.pos.x) + ", " + str(self.cell.pos.y) + ", " + color + ")"


# Snowball
class Snowball:
	def __init__(self, size):
		self.size = size


# Powdered Snow
class PowderedSnow:
	def __init__(self, size):
		self.size = size


# Tree
class Tree:
	pass


# Representation of a 2D point, used for playing field locations.
class Point:
    def __init__( self, xv, yv ):
        self.x = xv
        self.y = yv

	def __str__(self):
		return str("(" + str(self.x) + ", " + str(self.y) + ")")

    def set( self, vx, vy ):
        self.x = vx
        self.y = vy


# Representation for a child's action
class Move:
	def __init__(self, action="idle", dest=None):
		self.action = action
		self.dest = dest
	def __str__(self):
		return "Move(" + self.action + ", " + str(self.dest) + ")"


# Return the value of x, clamped to the [ a, b ] range.
def clamp( x, a, b ):
    if x < a:
        return a
    if x > b:
        return b
    return x


# Simulate a biased coin flip with probabily of heads = p
def coin_flip(p):
	x = random.randint(1, 100)
	return x <= int(p * 100)


# Starting point of the AI
def main():
	game = Game()
	game.start()

main()
